package evaluation;

import java.util.PriorityQueue;

/**
 * 已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离不可以超过k，并且k相对于数组来说比较小，请选择一个合适的排序算法针对这个数据进行排序
 */
public class HeadQuestion {
    public static void sort(int[] arr,int k){
        //默认小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int index = 0;
        for (; index<=Math.min(arr.length,k);index++){
            heap.add(arr[index]);
        }
        int i = 0;
        while (!heap.isEmpty()){
            arr[i++] = heap.poll();
        }
    }

    public static void main(String[] args) {
        int a[] = {1,4,5,7,2,3,9,6};
        sort(a,7);
        for (int i : a) {
            System.out.println(i);
        }
    }

}
